package com.zs.letcode.top_interview_question_medium;

import java.util.HashSet;
import java.util.Set;

/**
 * 相交链表
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * <p>
 * 图示两个链表在节点 c1 开始相交：
 * <p>
 * <p>
 * <p>
 * 题目数据 保证 整个链式结构中不存在环。
 * <p>
 * 注意，函数返回结果后，链表必须 保持其原始结构 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
 * 输出：Intersected at '8'
 * 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
 * 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
 * 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
 * 示例 2：
 * <p>
 * <p>
 * <p>
 * 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
 * 输出：Intersected at '2'
 * 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
 * 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
 * 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
 * 示例 3：
 * <p>
 * <p>
 * <p>
 * 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
 * 输出：null
 * 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
 * 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
 * 这两个链表不相交，因此返回 null 。
 *  
 * <p>
 * 提示：
 * <p>
 * listA 中节点数目为 m
 * listB 中节点数目为 n
 * 0 <= m, n <= 3 * 104
 * 1 <= Node.val <= 105
 * 0 <= skipA <= m
 * 0 <= skipB <= n
 * 如果 listA 和 listB 没有交点，intersectVal 为 0
 * 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
 *  
 * <p>
 * 进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？
 * <p>
 * 相关标签
 * 哈希表
 * 链表
 * 双指针
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xv02ut/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/10/9 06:56
 */
public class Chapter9 {

    /**
     * Definition for singly-linked list.
     */
    private class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    private class Solution {
        /**
         * 通过集合set解决
         *
         * @param headA
         * @param headB
         * @return
         */
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            //创建集合set
            Set<ListNode> set = new HashSet<>();
            //先把链表A的结点全部存放到集合set中
            while (headA != null) {
                set.add(headA);
                headA = headA.next;
            }

            //然后访问链表B的结点，判断集合中是否包含链表B的结点，如果包含就直接返回
            while (headB != null) {
                if (set.contains(headB)) {
                    return headB;
                }
                headB = headB.next;
            }
            //如果集合set不包含链表B的任何一个结点，说明他们没有交点，直接返回null
            return null;
        }

        /**
         * 先统计两个链表的长度
         */
        public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
            //统计链表A和链表B的长度
            int lenA = length(headA), lenB = length(headB);

            //如果节点长度不一样，节点多的先走，直到他们的长度一样为止
            while (lenA != lenB) {
                if (lenA > lenB) {
                    //如果链表A长，那么链表A先走
                    headA = headA.next;
                    lenA--;
                } else {
                    //如果链表B长，那么链表B先走
                    headB = headB.next;
                    lenB--;
                }
            }

            //然后开始比较，如果他俩不相等就一直往下走
            while (headA != headB) {
                headA = headA.next;
                headB = headB.next;
            }
            //走到最后，最终会有两种可能，一种是headA为空，
            //也就是说他们俩不相交。还有一种可能就是headA
            //不为空，也就是说headA就是他们的交点
            return headA;
        }

        private int length(ListNode node) {
            int length = 0;
            while (node != null) {
                node = node.next;
                length++;
            }
            return length;
        }

        /**
         * 双指针解决
         */
        public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
            //tempA和tempB我们可以认为是A,B两个指针
            ListNode tempA = headA;
            ListNode tempB = headB;
            while (tempA != tempB) {
                //如果指针tempA不为空，tempA就往后移一步。
                //如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB
                tempA = tempA == null ? headB : tempA.next;
                //指针tempB同上
                tempB = tempB == null ? headA : tempB.next;
            }
            //tempA要么是空，要么是两链表的交点
            return tempA;
        }
    }
}
